public class MyHashTable<K,V>{
    
    // 链表节点
    private static class Node<K,V>{
        K key;
        V value;
        Node next;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }

    private Node[] table;
    private int size;
    private static final int init_capacity = 0;
    
    public MyHashTable(){
        this(init_capacity);
    }
    
    public MyHashTable(int capacity){
        size = 0;
        table = new Node[capacity];
    }
    
    public Node put(K key, V value){
        int index = getIndex(key);
        if(table[index] == null){
            table[index] = new Node(key,value);
        }
        
        Node head = table[index];
        Node prev = null;
        while(head != null){
            prev = head;
            if(key.equals(head.key)){
                head.value = value;
                return head;
            }
        }
        Node newNode = new Node(key,value);
        prev.next = newNode;
        size++;
        if(size > table.length * 0.75){
            resize(table.length*2);
        }
        return newNode;
    }
    
    public Node remove(K key){
        int index = getIndex(key);
        if(table[index] == null){
            throw new IllegalArgumentException("没有该元素!");
        }
        
        Node head = table[index];
        Node prev = null;
        while(head != null){
            prev = head;
            if(head.key.equals(key)){
                prev.next = head.next;
                size--;
                return head;
            }
        }
        
        if(size <= table.length/8){
            resize(table.length/4);
        }
        return null;
    }
    
    
    public Node search(K key){
        int index = getIndex(key);
        Node head = table[index];
        
        while(head != null){
            if(key.equals(head.key)){
                return head;
            }
        }
        return null;
    }
    
    public void resize(int newCapacity){
        
    }
    
    
    public int getIndex(K key){
        return key.hashCode()% table.length;
    }
    
    
    
}